package LimitedTimeGame.Day_0224;

/**
 * @author zxc
 * @date 2023/02/24 09:56
 **/

/**
 * 题目 ：分割字符串s的方案数
 * 题目详述 ：
 * 给你一个二进制串s （一个只包含 0 和 1 的字符串），我们可以将 s分割成 3 个 非空字符串 s1, s2, s3 （s1 + s2 + s3 = s）。
 * 请你返回分割s的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。
 * 由于答案可能很大，请将它对 10^9 + 7 取余后返回。
 *
 * 提示：
 * s[i] == '0' 或者 s[i] == '1'
 * 3 <= s.length <= 10^5
 */
public class NumWays {
    public static void main(String[] args) {
        System.out.println(numWays("0000"));
    }
    /**
     * 思路 ：
     * （1）遍历整个二进制串s，来获取第一个非空字符串 && 同时记录下当前首个截取的非空字符串中1的数量;
     * （2）遍历后续字符串，截取第二个非空字符串，直至截取 和第一个非空字符串中1的数量一样为止;
     *  若是截取不到，则代表后面截取的字符串是必然不成立的;
     * （3）后续字符串，皆是第三个非空字符串，所以直接遍历第三个非空字符串，来判断第三个非空字符串中1的数量是否一致;
     *  若是后续字符串中1的数量 > 首个截取的字符串中1的数量的话，则将首个截取的非空字符串中1的数量 + 1;
     *  若是后续字符串中1的数量 < 首个截取的字符串中1的数量的话，则后续必然是不成立的;
     * @param s
     * @return
     */
    public static int numWays(String s) {
        int len = s.length();
        // 统计最终结构
        long sum = 0;
        // 统计首个字符串index中1的数量
        int count = 0;
        // 在首个字符串中1的数量不变的情况下，统计所有可能的情况;
        long oneCount = 1;
        //在第二个字符串中1的数量不变的情况下，统计所有可能的情况;
        long twoCount = 1;
        for(int i = 0 ; i < len ; i++){
            // 若是所截取的三个非空字符串不满足条件的话，则需要对于变量oneCount && twoCount重新进行初始化;
            oneCount = 1;
            twoCount = 1;
            // 特殊情况 ：即，若是所有都是0的可能情况
            if(count == 0){
                while(i < len){
                    if(s.charAt(i) == '1'){
                        break;
                    }
                    i++;
                }
                if(i == len){
                    // 注意 ：需要使用long类型来进行获取结果，否则会出现溢出情况;
                    for(int m = 1 ; m <= len - 2 ;m++){
                        sum += m;
                    }
                    sum = sum % 1000000007;
                }
            }
            // 首个字符串中所截取字符中 1的数量加1;
            if(i < len && s.charAt(i) == '1'){
                // 变量count，用来统计首个字符串中 1的数量;
                count++;
                // 在 首个字符串中1的数量不变的情况下，统计所有可能的情况，同时使用oneCount变量进行保存;
                while(i + 1 < len && s.charAt(i + 1) == '0'){
                    i++;
                    oneCount++;
                }
                // 情况一 ：当首个截取的非空字符串中 1的数量 * 2 > 后续字符串长度，则必然不可能;
                if(2 * count > len - i){
                    break;
                }
                // 使用临时变量temp，来记录首个截取字符串中1的数量;
                int temp = count;
                for(int j = i + 1 ; j < len ; j++){
                    if(s.charAt(j) == '1'){
                        temp--;
                    }
                    if(count + temp > len - j){
                        break;
                    }
                    // 若是 temp == 0，就没必要在对于第二个截取的非空字符串继续进行遍历;
                    if(temp == 0){
                        int threeCount = 0;
                        // 第二个字符串中1的数量不变的情况下，统计所有可能的情况，同时使用twoCount变量进行保存;
                        while(j + 1 < len && s.charAt(j + 1) == '0'){
                            twoCount++;
                            j++;
                        }
                        if(count > len - j){
                            break;
                        }
                        // 统计最后一个非空字符串中1的数量;
                        for(int k = j + 1 ; k < len ; k++){
                            if(s.charAt(k) == '1'){
                                threeCount++;
                            }
                        }
                        // 若是最后一个非空字符串中1的数量 == 首个非空字符串中1的数量的话，则找到合适的截取方式：
                        if(threeCount == count){
                            // 注意 ：需要将oneCount && twoCount 变量设置为long类型，若是使用int类型进行存储的话，极有可能溢出;
                            sum += oneCount * twoCount % 1000000007;
                        }
                        break;
                    }
                    // 即，由于二进制串s是固定的，所以划分为三个非空字符串时，各个字符串所拥有的1的数量是固定的;
                    if(sum != 0){
                        break;
                    }
                }
            }
        }
        return (int)sum;
    }
}
